package sort;

import java.rmi.server.RMIClassLoader;
import java.util.*;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User:周次煜
 * Date: 2024-04-14
 * Time：14:19
 */
public class MySort {
     /**
      * 插入排序
      * 先放置在 i 之后成立的数进行移位
      * 然后插入最后不成立的数和成立的数中间
      * 时间复杂度： O(n^2)
      * 空间复杂度： O(1)
      * 稳定性： 稳定
      * @param array
      */

    // 插入排序
     public static void insertSort(int[]array) {
          int j=0,tmp=0;
          for (int i = 1; i < array.length; i++) {
               j=i-1;
               tmp=array[i];
               for (; j >= 0 ; j--) {
                    if (array[j] > tmp) {
                         array[j+1]=array[j];
                    } else {
                         break;
                    }
               }

               array[j+1]=tmp;
          }
     }

     public static void insertSort(int[]array,int start,int end) {
          int j=0,tmp=0;
          for (int i = start+1; i <= end; i++) {
               j=i-1;
               tmp=array[i];
               for (; j >= start ; j--) {
                    if (array[j] > tmp) {
                         array[j+1]=array[j];
                    } else {
                         break;
                    }
               }

               array[j+1]=tmp;
          }
     }


     /**
      * 插入排序的优化版：
      * 希尔排序
      * 先分组，后插入排序
      * 组数为 j的跳跃跨度
      * 时间复杂度：O（N^1.3）
      * 空间复杂度：O(1)
      * 稳定性：不稳定
      */

     public static void shellSort( int[] array) {
          int gap=array.length;
          while (gap >= 1) {
               gap /= 2;
               shellFunc(array,gap);
          }
     }

     private static void shellFunc(int[]array ,int gap) {
          int j=0,tmp=0;
          for (int i = gap; i < array.length; i++) {
               j=i-gap;
               tmp=array[i];
               for (; j >=0 ; j -= gap) {
                    if (array[j]>tmp) {
                         array[j+gap]=array[j];
                    } else {
                         break;
                    }
               }
               array[j+gap]=tmp;
          }
     }

     /**
      * 选择排序
      * 在其后面筛选最大或最小值的小标进行替换
      * 无论数字是否有序,时间复杂度都一样
      * 时间复杂度 ： O(N^2)
      * 空间复杂度 ：O(1)
      * 稳定性： 不稳定
      */


     public static void selectSort(int [] array) {
          int minIndex=0;
          int j=0;
          for (int i = 0; i < array.length-1; i++) {
               minIndex=i;
               j=i+1;
               for (; j < array.length ; j++) {
                    if (array[j] < array[minIndex]) {
                         minIndex=j;
                    }
               }
               swap(array,minIndex,i);
          }
     }


     /**
      * 插入排序2
      * 利用左边是最小值的小标
      * 右边是最大值的下标
      * 注意一点:交换最小值有可能会影响最大值的交换
      * 需要判断
      * 时间复杂度:O(n^2)
      * 空间复杂度:O(1)
      * 稳定性: 不稳定
      * @param array 待排序数组
      */

     public  static  void selectSort2(int []array) {
          int left=0;
          int right=array.length-1;
          int j=0,maxIndex=0,minIndex=0;
          while (left < right) {
               minIndex=left;
               maxIndex=right;
               for ( j = left; j <= right; j++) {
                    if (array[j]<array[minIndex]) {
                         minIndex=j;
                    }

                    if (array[j]>array[maxIndex]) {
                         maxIndex=j;
                    }
               }

               swap(array,left,minIndex);
               if (maxIndex==left) {
                    maxIndex= minIndex;
               }

               swap(array,right,maxIndex);
               left++;
               right--;
          }
     }
     /**
      * 交换的四种方式
      * @param array ： 需要交换的数组
      * @param x ： 左边个小标
      * @param y： 右边下标
      */

     private static void swap(int[]array,int x,int y) {

          // 双变量赋值
          int a=array[x];
        int b=array[y];

          array[x]=b;
          array[y]=a;

//          a = a ^ b;  // a^b=0
//          b = a ^ b;  // --> a^b^b =a  0^a=a
//          a = a ^ b;  // --> a^b^a =b  0^a=a;


          /**
           * 错误的交换方法
           * 不可用下标引用交换
           * 若下标相同
           * 下标引用时值两个值都会改变
           */

//          array[x]=array[x]^array[y];
//          array[y]=array[x]^array[y];
//          array[x]=array[x]^array[y];



          // 和差交换
//          a = a + b;
//          b = a - b;
//          a = a - b;
//


          // 常规交换
//          int tmp=array[x];
//          array[x]=array[y];
//          array[y]=tmp;
     }

     /**
      * 堆排序 : 利用 大根堆的队头元素 是最大的 插入至最后
      *  将其放在最后面,再重新制造大根堆
      *  时间复杂度: O(N*long(N))
      *  空间复杂度: O(1)
      *  稳定性: 不稳定
      */

     public static void heapSort(int[] array ) {
          int parent = (array.length-2)/2;
          for (;  parent >= 0 ;parent--) {
               createHeap(array,parent);
          }
          for (int i = array.length-1; i >= 0 ; i--) {
               heapFunc(array,i);
          }
     }


     private  static void createHeap(int[]array,int parent) {
          int child= (parent*2)+1;
          while (child < array.length) {

               if (child+1 < array.length && array[child]<array[child+1]) {
                    child++;
               }

               if (array[child]>array[parent]) {
                    swap(array,child,parent);

               } else {
                   break;
               }

               parent = child;
               child = parent*2+1;
          }
     }


     private static void heapFunc(int[]array,int index) {
          swap(array,0,index);
          index--;
          int parent = 0;
          int child = parent*2+1;
          while (child <= index) {
               if (child+1 <= index && array[child] < array[child+1]) {
                    child++;
               }
               if (array[child] >array[parent]) {
                    swap(array,child,parent);
               } else {
                    break;
               }
               parent=child;
               child=parent*2+1;
          }
     }


     /**
      * 冒泡排序
      * 利用把每一个元素都旁边元素进行交换 得出依次大小的排序
      * 时间复杂度: O(N^2)
      * 空间复杂度: O(1)
      * 稳定性: 稳定
      */

     public  static void  bubbleSort(int[]array) {

          // 先建立一个标志
          boolean b=true;
          for (int i = 0; i < array.length-1; i++) {

               for (int j = 0; j < array.length-1-i; j++) {
                    if (array[j] > array[j+1]) {
                         swap(array,j,j+1);
                         // 这趟只要交换了, 令true
                         b=false;
                    }
               }

               // 一旦这趟下来没有交换，就证明有序
               if (b) {
                    break;
               }
          }
     }


     /**
      * 快速排序 普通版本
      * @param array
      * 时间复杂度 ： O(N * logN)
      * 空间复杂度 ： O(logN)
      * 稳定性： 不稳定
      */

     public static void fastSort(int[]array) {
          // 普通版快排
//          fastSortFunc(array,0,array.length-1);

          // 优化版快排
          fastSortFuncBetter(array,0,array.length-1);

          // 非递归快排
//          fastSortFuncNo(array,0,array.length-1);

     }

     private static void fastSortFunc(int[]array,int start,int end) {
          if (start >= end) {
               return;
          }

          int index=findSpeedIndex(array,start,end);

          // 先递归左边数
          fastSortFunc(array,start,index-1);

          // 再递归右边数
          fastSortFunc(array,index+1,end);
     }


     /**
      *  Hoare 法
      *  前后指针法
      *  前面遇到大的数, 后面遇到小的数就交换
      * @param array 数组
      * @param left 左下标
      * @param right 右下标
      * @return  返回一个相遇的下标
      */

     //
     private static int findHoareIndex(int[]array,int left,int right) {
          int tmp=array[left];
          int flg=left;

          /**
           * 1.注意先右后左，因为左边有可能会在直接等于右边， 相等时有可能是个很大数 ，否则就会把大的值放在前面
           * 2. 注意都得取等号，因为左右两边有可能想等
           * 3.每个独立的循环，都要注意下标是否会越界
           */

          while (left < right) {


               while (left<right && array[right] >= tmp) {
                    right--;
               }
               while (left<right &&array[left] <= tmp) {
                    left++;
               }

               swap(array,right,left);
          }

          // 最终两者相遇
          swap(array,left,flg);
          return right;

     }


     // 挖坑法
     private static int findHoleIndex(int[]array,int left,int right) {
          int tmp=array[left];
          int flg=left;

          /**
           * 1.注意先右后左，因为左边有可能会在直接等于右边， 相等时有可能是个很大数 ，否则就会把大的值放在前面
           * 2. 注意都得取等号，因为左右两边有可能想等
           * 3.每个独立的循环，都要注意下标是否会越界
           */

          while (left < right) {


               while (left<right && array[right] >= tmp) {
                    right--;
               }

               array[left]=array[right];

               while (left<right &&array[left] <= tmp) {
                    left++;
               }

               array[right]=array[left];
          }

          // 最终两者相遇
          array[left]=tmp;
          return right;

     }


     // 快慢指针法

     /**
      * 快慢指针法
      * @param array 指定数组
      * @param left 基准值,起始值
      * @param right 右边界
      * @return 最终 slow 慢指针停下的位置
      *
      * 快慢指针的含义：
      * slow 找 小的值
      * fast 找 大的值 ，并和慢指针进行交换
      *
      */

     private  static  int findSpeedIndex(int []array,int left,int right) {
          int slow=left;
          int fast=slow+1;
          int tmp=array[left];


          while (fast <= right) {
               // 慢的先 ++
               slow++;

               // 如果 快的小于 基准值
               if (array[fast] < tmp ) {

                    // 并且不等于慢的值
                    if ( fast != slow) {
                         swap(array,slow,fast);
                    }

               } else  {
                    // 如果没遇到就 slow 停下一步
                    slow--;
               }

               // fast 向右走
               fast++;

          }

          // 最终 slow 和 基准值 交换
          swap(array,left,slow);

          return slow;
     }


     /**
      * 快速排序的优化版
      *  利用中间下标然后再得到中间元素下标
      *  返回该下标
      */



     private static void fastSortFuncBetter(int[]array,int start,int end) {
          if (start >= end) {
               return;
          }




          int middleIndex=findMiddleIndex(array,start,end);

          swap(array,start,middleIndex);

//          if ((end-start) + 1 <= 10) {
//               insertSort(array,start,end);
//               return;
//          }



          int index = findSpeedIndex(array,start,end);



          // 先递归左边数
          fastSortFuncBetter(array,start,index-1);
          fastSortFuncBetter(array,index+1,end);
     }

     /**
      * 三数取中法
      * @param array 数组
      * @param left 左边界
      * @param right 右边界
      * @return 返回中间下标
      */

     private static int findMiddleIndex(int[]array,int left,int right) {
          int middle=left + (right-left) >>>1;

          if (array[left] < array[right]) {
               if (array[left] > array[middle]) {
                    return left;
               } else if (array[right] < array[middle]) {
                    return right;
               }
          } else {
               if (array[right] > array[middle]) {
                    return right;
               } else if (array[left] < array[middle]) {
                    return left;
               }
          }

          return middle;

     }


     /**
      *
      *  非递归快排
      * @param array 数组
      * @param left 左边下标
      * @param right 右边下标
      *  时间复杂度： O(N*log(N))
      *  空间复杂度： O(log(N))
      *  稳定性： 不稳定
      */

     public  static  void  fastSortFuncNo(int[]array,int left,int right) {

          Stack<Integer> stack=new Stack<>();

          // 先得到一次基准下标
          int par = findHoleIndex(array,left,right);

          if (right-1>par) {
               stack.push(par+1);
               stack.push(right);
          }

          if (left+1 < par) {
               stack.push(left);
               stack.push(par-1);
          }

          /**
           * 当栈不为空时
           * 当栈不为空时就意味着中间没有元素可以入栈了
           * 之后就会排序完成
           *
           */

          while (!stack.empty()) {

               // 先出栈右边下标
               right=stack.pop();

               // 再出栈左边下标
               left=stack.pop();


               par = findHoleIndex(array,left,right);

               // 右边到基准的距离
               if (right-1>par) {
                    stack.push(par+1);
                    stack.push(right);
               }


               // 左边 到 基准的距离

               if (left+1 < par) {
                    stack.push(left);
                    stack.push(par-1);
               }
          }
     }

     /**
      * 归并排序
      * 把整体
      */

     public  static void mergeSort(int[] array) {
          int[]tmp=new int[array.length];
//          mergeSortFunc(array,0,array.length-1,tmp);
          mergeSortFuncNo(array,0,array.length-1,tmp);

     }

     /**
      * 归并排序递归法
      * @param array 数组
      * @param left 左边界
      * @param right 右边界
      * @param tmp 临时数组
      *
      */
     private static void mergeSortFunc(int[]array,int left,int right,int[] tmp) {
          if (left >= right) {
               return;
          }

          // 得到中间数
          int middle= (left+right)>>>1;

          // 中间的左边递归
          mergeSortFunc(array,left,middle,tmp);

          // 中间的右边递归
          mergeSortFunc(array,middle+1,right,tmp);

          int left1=left,right1=middle;
          int left2=middle+1,right2=right;
          int k=left1;

          // 循环抽取每个子区别最小数
          while (left1 <= right1 && left2 <= right2) {
               if (array[left1] < array[left2]) {
                    tmp[k]=array[left1];
                    left1++;
               } else  {
                    tmp[k]=array[left2];
                    left2++;
               }
               k++;
          }

          // 多出来的继续放入
          while (left1 <= right1) {
               tmp[k]=array[left1];
               left1++;
               k++;
          }

          while (left2 <= right2) {
               tmp[k]=array[left2];
               left2++;
               k++;
          }

          // 拷贝回去
          for (int l = left; l <= right ;l++) {
               array[l]=tmp[l];
          }
     }

     /**
      * 归并排序（非递归）
      * @param array 数组
      * @param left  左标
      * @param right 右标
      * @param tmp  临时数组
      * 这个未使用栈的循环非递归是比较轻巧的
      *  但需要注意下标问题
      *  不完整的最大边界有可能会溢出
      *  就需要手动调整为 数组大小
      *  如果连起始值都越界直接跳出
      */
     private static void mergeSortFuncNo(int[]array,int left,int right,int[] tmp) {

          int gap=1;

          // 从 gap 不断分组
          while (gap <= right) {
               mergeFunNo(array,left,right,gap,tmp);
               gap*=2;
          }

     }


     private static void mergeFunNo(int[]array,int left,int right,int gap,int[] tmp) {

          int left1=0;
          int right1=0;
          int left2=0;
          int right2=0;


          int index=0;

          for (int i = 0; i <= right; i += 2*gap) {
               left1=i;
               right1=i+gap-1;
               left2=i+gap;
               right2=i+2*gap-1;
               if (left2 > right) {
                    break;
               }

               if (right2 > right) {
                    right2=right;
               }

               while (left1 <= right1 && left2 <= right2) {


                    if (array[left1] < array[left2]) {
                         tmp[index]=array[left1];
                         left1++;
                    } else {
                         tmp[index]=array[left2];
                         left2++;
                    }
                    index++;
               }

               while (left1 <= right1) {
                    tmp[index]=array[left1];
                    left1++;
                    index++;

               }

               while (left2 <= right2) {
                    tmp[index]=array[left2];
                    left2++;
                    index++;

               }

          }

          for (int i = 0; i < index; i++) {
               array[i]=tmp[i];
          }
     }


     /**
      * 计数排序
      * 利用哈希映射下标的原理进行排序
      *  时间复杂度： O(N+length)
      *  空间复杂度： O(length)
      *  稳定性： 稳定
      */

     public static void countSort(int [] array) {
          int sz=array.length;

          // 找出最大值和最小值
          int max=array[0],min=array[0];
          for (int k = 1; k < sz; k++) {
               if (array[k] >max) {
                    max=array[k];
               }
               if (array[k] < min) {
                    min=array[k];
               }
          }

          // 这里计算的是宽度，tmp数组的长度，必须+1
          int length=max-min+1;

          int []tmp=new int[length];

          // 进行哈西映射
          for (int i = 0; i < sz; i++) {
               tmp[array[i]-min]++;
          }

          int count=0,l=0;

//          然后进行赋值
          for (int j = 0; j < length; j++) {
               count=tmp[j];
               while (count != 0) {
                    array[l]=j+min;
                    l++;
                    count--;
               }

          }
     }

     /**
      * 基数排序
      */

     public static void radixSort(int[]array) {

          ArrayList<Queue<Integer>> bucket=new ArrayList<>();

          // 创建 9 个 桶
          for (int i = 0; i < 10; i++) {
               bucket.add(new LinkedList<>());
          }

          // 寻找最大数
          int max=array[0];
          for (int i = 1; i <array.length ; i++) {
               if (array[i]>max) {
                    max=array[i];
               }
          }

          // 得到最大位数
          int maxCount=0;
          while (max > 0) {
               maxCount++;
               max /= 10;
          }

          int m=0,n=1,index=0,p=0;
          while (maxCount > 0) {
               index=0;
               for (int i = 0; i < array.length; i++) {
                    m=array[i];
                    m /= n;
                    m %= 10;
                    Queue<Integer> queue=bucket.get(m);
                    queue.add(array[i]);
               }

               for (int j = 0; j < 10; j++) {
                    Queue<Integer> queue=bucket.get(j);
                    while (queue.size() > 0) {
                         array[index]= queue.poll();
                         index++;
                    }               }


               n *= 10;
               maxCount--;
          }
     }


     /**
      * 桶排序
      */
     public  static void bucketSort(int[]array) {
          ArrayList<Queue<Integer>> arrayLists= new ArrayList<>();

          // 寻找最大数
          int max=array[0];
          for (int i = 1; i <array.length ; i++) {
               if (array[i]>max) {
                    max=array[i];
               }
          }

          // 得到最大位数
          int maxCount=0;
          while (max > 0) {
               maxCount++;
               max /= 10;
          }

          for (int i = 0; i < Math.pow(10,maxCount-1); i++) {
               arrayLists.add(new LinkedList<>());
          }

          int m=0;

          for (int i = 0; i < array.length; i++) {
               m=array[i];
               m/=10;
               Queue<Integer> queue=arrayLists.get(m);

               queue.add(array[i]);
          }

          int index=0,sz=0,l=0;
          for (int j = 0; j < arrayLists.size(); j++) {
               Queue<Integer> queue=arrayLists.get(j);
               sz=queue.size();
               int[]tmp=new int[sz];
               index=0;
               for (int k = 0; k <sz ; k++) {
                    tmp[index]=queue.poll();
                    index++;
               }
               insertSort(tmp);

               for (int z = 0; z < sz; z++) {
                     array[l]=tmp[z];
                     l++;
               }
          }
     }
}
